package huffmanCode;

import java.util.*;
public class HuffmanCode {

  public static void main(String[] args) {
    String str = "i like like like java do you like a java";
    byte[] strBytes = str.getBytes();

    //分布过程
    /*List<Node> nodes = getNodes(strBytes);
    //创建赫夫曼编码树
    Node huffmanTree = createHuffmanTree(nodes);
    huffmanTree.preOrder();

    //获取赫夫曼编码表
    getHuffmanCode(huffmanTree,"",stringBuilder);
    System.out.println(huffmanCode);

    //获取赫夫曼编码压缩后的byte[]
    byte[] zipCode = zip(strBytes, huffmanCode);
    System.out.println(Arrays.toString(zipCode));*/

    byte[] zipCode = huffmanCodeZip(strBytes);
    System.out.println(Arrays.toString(zipCode));
  }

  static Map<Byte,String> huffmanCode=new HashMap<>();
  static StringBuilder stringBuilder=new StringBuilder();



  public static byte[] huffmanCodeZip(byte[] strBytes){
    //获取node的集合
    List<Node> nodes = getNodes(strBytes);
    //创建赫夫曼树
    Node huffmanTreeNode = createHuffmanTree(nodes);
    //获取赫夫曼编码的map
    getHuffmanCode(huffmanTreeNode,"",stringBuilder);
    //生成压缩后的赫夫曼编码表
    byte[] zipCode = zip(strBytes, huffmanCode);
    return zipCode;
  }

  //获取赫夫曼编码
  public static void getHuffmanCode(Node node,String code,StringBuilder stringBuilder) {
    StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
    stringBuilder1.append(code);
    if (node!=null){
      if (node.data==null){
        getHuffmanCode(node.left,"0",stringBuilder1);
        getHuffmanCode(node.right,"1",stringBuilder1);
      }else {
        huffmanCode.put(node.data,stringBuilder1.toString());
      }
    }
  }

  //获取赫夫曼编码压缩后的byte[]
  public static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCode){
    StringBuilder stringBuilder = new StringBuilder();
    for (byte key : bytes) {
      stringBuilder.append(huffmanCode.get(key));
    }

    int length;//压缩后的byte[]长度，一个字节为单位
    if (stringBuilder.length()%8==0){
      length=stringBuilder.length()/8;
    }else {
      length=stringBuilder.length()/8+1;
    }

    byte[] huffmanCodeBytes = new byte[length];
    int index=0;
    for (int i=0;i<stringBuilder.length();i+=8){
      String str;
      if (i+8<stringBuilder.length()){
        str = stringBuilder.substring(i, i + 8);
      }else {
        str=stringBuilder.substring(i);
      }
      huffmanCodeBytes[index]= (byte) Integer.parseInt(str,2);
      index++;
    }
    return huffmanCodeBytes;
  }

  // 获得结点的list
  public static List<Node> getNodes(byte[] bytes) {
    ArrayList<Node> list = new ArrayList<Node>();
    HashMap<Byte, Integer> map = new HashMap<>();
    for (Byte data : bytes) {
      map.merge(data, 1, Integer::sum);
    }
    for (Map.Entry<Byte, Integer> entrySet : map.entrySet()) {
      list.add(new Node(entrySet.getKey(), entrySet.getValue()));
    }
    return list;
  }

  public static Node createHuffmanTree(List<Node> nodes) {
    Collections.sort(nodes);
    while (nodes.size()>1){
      Node leftNode = nodes.get(0);
      Node rightNode = nodes.get(1);
      Node parent=new Node(null,leftNode.weight+rightNode.weight);
      parent.left=leftNode;
      parent.right=rightNode;
      nodes.add(parent);
      nodes.remove(leftNode);
      nodes.remove(rightNode);
      Collections.sort(nodes);
    }
    return nodes.get(0);
  }
}

class Node implements Comparable<Node> {
  Byte data;
  Integer weight;
  Node left;
  Node right;

  public Node(Byte data, Integer weight) {
    this.data = data;
    this.weight = weight;
  }

  @Override
  public String toString() {
    return "Node{" + "data=" + data + ", weight=" + weight + '}';
  }

  @Override
  public int compareTo(Node o) {
    return this.weight - o.weight;
  }

  public void preOrder(){
    System.out.println(this);
    if (this.left!=null){
      this.left.preOrder();
    }
    if (this.right!=null){
      this.right.preOrder();
    }
  }
}
